/* ************************************************************************
> File Name:     SqList.cpp
# Author:        
# mail:          
> Created Time:  2023年02月13日 星期一 20时25分40秒
> Description:   
 ************************************************************************/

#include "../include/SqList.h"

int isTrue(string str)
{
    int m = 0;
    if (str[0] == '-')          //输入为负数
    {
        for (size_t i = 1; i < str.length(); i++)
        {
            if (str[i] >= '0' && str[i] <= '9')
                continue;
            else
            {
                cout << "输入的数据中含有非数字" << endl << endl;
                return -1;
            }
        }
    }
    else
    {
        for (size_t i = 0; i < str.length(); i++)
        {
            if (str[i] >= '0' && str[i] <= '9')
                continue;
            else
            {
                cout << "输入的数据中含有非数字" << endl << endl;
                return -1;
            }
        }
    }
    //将str转换为int类型   注意输入的数据不能超过
    m = stoi(str);
    return m;
}

template <typename T>
void Quick_Sort(Sqlist<T> &array, int Start_Index, int End_Index) {
     if(End_Index >= Start_Index) {
        int first = Start_Index;
        int last = End_Index;
        T key = array.index(first);
        while (first < last) {
            while (first < last && array.index(last) >= key) {
                last--;
            }
            array.replace(first, array.index(last));
            while (first < last && array.index(first) <= key) {
                first++;
            }
            array.replace(last, array.index(first));
        }
        array.replace(first, key);
        Quick_Sort(array, Start_Index, first - 1);
        Quick_Sort(array, first + 1, End_Index);
    }
}

template <typename T>
Sqlist<T> mergeSqlist(Sqlist<T> &l1, Sqlist<T> &l2)
{
    Sqlist<T> l;
    l.Init_Sqlist();
    set<T> uset;
    for(int i = 1; i <= l1.Getlen(); i++) uset.insert(l1.index(i));
    for(int i = 1; i <= l2.Getlen(); i++) uset.insert(l2.index(i));
    for(int i : uset) cout << i << " ";
    cout << endl;
    return l;
}

template <typename T>
Sqlist<T> intersectSqlist(Sqlist<T> &l1, Sqlist<T> &l2)
{
    Sqlist<T> l;
    l.Init_Sqlist();
    for(int i = 1; i <= l1.Getlen(); i++)
    {
        for(int j = 1; j <= l2.Getlen(); j++)
        {
            if(l1.index(i) == l2.index(j))
            {
                l.insert(l1.index(i));
                break;
            }
        }
    }
    return l;
}

void MySqList() {
    Sqlist<int> l1, l2;
    l1.Init_Sqlist();
    l2.Init_Sqlist();
    cout << "请输入顺序表一，例如 1 2 3 4 ..." << endl;
    string x;
    while(cin >> x)
    {
        int m = isTrue(x);
        if(m != -1)
        {
            l1.insert(m);
        }
        else 
        {
            return;
        }
        if(cin.get() == '\n') break;
    }
    cout << "请输入顺序表二，例如 1 2 3 4 ..." << endl;
    while(cin >> x)
    {
        int m = isTrue(x);
        if(m != -1)
        {
            l2.insert(m);
        }
        else 
        {
            return;
        }
        if(cin.get() == '\n') break;
    }
    cout << endl;
    cout << "现在顺序表一为：" << endl;
    l1.traverse(print);
    cout << "现在顺序表二为：" << endl;
    l2.traverse(print);
    cout << endl << "顺序表一排序后：" << endl;
    Quick_Sort(l1, 1, l1.Getlen());
    l1.traverse(print);
    cout << "顺序表二排序后：" << endl;
    Quick_Sort(l2, 1, l2.Getlen());
    l2.traverse(print);
    cout << endl;
    cout << "两个顺序表排序后：" << endl;
    Sqlist<int> l4 = mergeSqlist(l1, l2);
    cout << endl << "两个顺序表的交集为：" << endl;
    Sqlist<int> l3 = intersectSqlist(l1, l2);
    l3.traverse(print);
    cout << endl;
}
